package basic.basic_class05;

import java.util.HashMap;
import java.util.List;

public class Code_04_UnionFind {

    //节点类
    public static class Node{
        // 自定义并查集结构中操作的对象
    }

    public static class UnionFindSet{
        private HashMap<Node,Node> fatherMap;    // key:当前节点， value当前节点的父节点
        private HashMap<Node,Integer> sizeMap;   // 表示当前节点所在集合的大小

        //空参构造器,构造并查集结构
        public UnionFindSet(){
            fatherMap = new HashMap<Node,Node>();
            sizeMap = new HashMap<Node,Integer>();
        }

        //初始化并查集结构之前必须加入样本集
        public void makeSets(List<Node> nodes) {
            fatherMap.clear();    // 清空操作，避免之前记录影响
            sizeMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node,node);
                sizeMap.put(node,1);
            }
        }

        //查找指定Node的代表节点（递归操作，将沿途的所有节点都加到父节点下面去）
        public Node findFather(Node node) {
            Node father = fatherMap.get(node);
            if(father != node) {
                // 如果当前的节点和node不一样，表示node不是代表节点，则递归求node上一层的代表节点
                father = findFather(father);
            }
            // 走到这里father已经是确定的值了，将沿途得所有node改为father就可以了
            fatherMap.put(node,father);
            return father;
        }

        //判断两个节点是否属于同一集合(只需要判断两个节点是否有一样的代表节点即可)
        public boolean isSameSet(Node a, Node b) {
            return findFather(a) == findFather(b);
        }

        //合并两个集合
        public void Union(Node a, Node b) {
            if(a == null || b == null) return;
            // 首先查找出两个集合得代表节点
            Node aHead = findFather(a);
            Node bHead = findFather(b);
            // 如果不在同一个集合，则合并
            if(aHead != bHead){
                // 分别获取两个集合得代表节点所存储的集合大小
                int aSize = sizeMap.get(aHead);
                int bSize = sizeMap.get(bHead);
                // 如果a集合数量小于等于b，那么将a集合的代表节点加到b集合的代表节点中去
                if(aSize <= bSize) {
                    fatherMap.put(aHead,bHead);
                    sizeMap.put(bHead,aSize + bSize);
                }else{
                    fatherMap.put(bHead,aHead);
                    sizeMap.put(aHead,aSize + bSize);
                }
            }
        }
    }
}
